package leetcode_day._2023._11;

/**
 * 2304.网格中的最小路径代价 <br />
 * 算法: 动态规划
 *
 * @author yezh
 * @date 2023/11/22 14:33
 */
public class _22 {

    // 动态规划
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int ans = Integer.MAX_VALUE, m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) dp[0][i] = grid[0][i];
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) tmp = Math.min(tmp, moveCost[grid[i - 1][k]][j] + dp[i - 1][k]);
                dp[i][j] = tmp + grid[i][j];
            }
        }
        for (int i = 0; i < n; i++) ans = Math.min(ans, dp[m - 1][i]);
        return ans;
    }

    // 空间复杂度为 O(1) 的动态规划
    public static int minPathCost_optimize(int[][] grid, int[][] moveCost) {
        int ans = Integer.MAX_VALUE, m = grid.length, n = grid[0].length;
        for (int i = m - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int tmp = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) tmp = Math.min(tmp, moveCost[grid[i][j]][k] + grid[i + 1][k]);
                grid[i][j] += tmp;
            }
        }
        for (int i = 0; i < n; i++) ans = Math.min(ans, grid[0][i]);
        return ans;
    }

    // 记忆化搜索
    public int minPathCost_dfs_memo(int[][] grid, int[][] moveCost) {
        int ans = Integer.MAX_VALUE;
        int[][] memo = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid[0].length; i++) ans = Math.min(ans, dfs_memo(0, i, grid, moveCost, memo));
        return ans;
    }

    int dfs_memo(int i, int j, int[][] grid, int[][] moveCost, int[][] memo) {
        int m = grid.length, n = grid[0].length;
        if (i == m - 1) return grid[i][j];
        if (memo[i][j] != 0) return memo[i][j];
        int tmp = Integer.MAX_VALUE;
        for (int k = 0; k < n; k++) tmp = Math.min(tmp, dfs_memo(i + 1, k, grid, moveCost, memo) + moveCost[grid[i][j]][k]);
        return tmp + grid[i][j];
    }

}
